package leetcode.top100;


import utils.TreeNode;

import java.util.Arrays;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 类似题见{@link offerbook.Code06_ReConstructBT_二叉树重建}
 * 类似题见{@link offerbook.Code24_ReconstructBST}
 * @date 2020/4/7 17:34
 */
public class Code105_ReconstructBT {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) return null;
        if(inorder == null || inorder.length == 0) return null;
        assert preorder.length == inorder.length;
        int rootVal = preorder[0];
        int index = 0;
        while (index < preorder.length){
            if(inorder[index] == rootVal) break;
            index++;
        }
        if(index == preorder.length) throw new RuntimeException("illegal");
        TreeNode treeNode = new TreeNode(rootVal);
        treeNode.left = buildTree(Arrays.copyOfRange(preorder,1,index+1),
                Arrays.copyOfRange(inorder,0,index));
        treeNode.right = buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),
                Arrays.copyOfRange(inorder,index+1,inorder.length));
        return treeNode;
    }
}
